// Problem: 天使玩偶
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/256/
// Memory Limit: 256 MB
// Time Limit: 7000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include<bits/stdc++.h>
using namespace std;

namespace IO{
    int f; char c;

    template<typename T> inline void read(T &v){
        v = 0; f = 1; c = getchar();
        while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
        while(isdigit(c)) { v = (v << 3) + (v << 1) + (int)(c - '0'); c = getchar(); }
        v *= f;
        return;
    }

    template<typename T> inline void write(T k){
        if(k < 0) { putchar('-'); k = -k; }
        if(k > 9) write(k / 10);
        putchar((char)(k % 10 + '0'));
        return;
    }

    inline int Read() { int v; read(v); return v; }
    inline void Write(int v, char ed = '\n') { write(v); putchar(ed); return; }
}

#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)

using IO::read;
using IO::Write;

const int N=1e6+5, INF=0x3f3f3f3f;

struct Point{
    int x[2];
};

struct Node{
    int l, r;
    Point P;
    int L[2], R[2], sz;

    #define ls tr[u].l
    #define rs tr[u].r
}tr[N];

int n, m;

int idx, root;
int buf[N], tot;
int add(){
    if(!tot) return ++idx;
    return buf[tot--];
}

void pushup(int u){
    auto &L=tr[ls], &R=tr[rs];
    tr[u].sz=L.sz+R.sz+1;

    rep(i,0,1){
        tr[u].L[i]=min(tr[u].P.x[i], min(L.L[i], R.L[i]));
        tr[u].R[i]=max(tr[u].P.x[i], max(L.R[i], R.R[i]));
    }
}

const double Al=0.75;

Point pt[N];

void getSeq(int u, int cnt){
    if(ls) getSeq(ls, cnt);
    buf[++tot]=u, pt[tr[ls].sz+1+cnt]=tr[u].P;
    if(rs) getSeq(rs, cnt+tr[ls].sz+1);
}

int rebuild(int l, int r, int k){
    if(l>r) return 0;
    int mid=l+r>>1;
    int u=add();

    nth_element(pt+l, pt+mid, pt+r+1, [&](Point a, Point b){
        return a.x[k]<b.x[k];
    });
    tr[u].P=pt[mid];

    ls=rebuild(l, mid-1, k^1), rs=rebuild(mid+1, r, k^1);
    pushup(u);
    return u;
}

void maintain(int &u, int k){
    if(tr[u].sz*Al<tr[ls].sz || tr[u].sz*Al<tr[rs].sz)
        getSeq(u, 0), u=rebuild(1, tot, k); 
}

void insert(int &u, Point p, int k){
    if(!u){
        u=add();
        tr[u].l=tr[u].r=0;
        tr[u].P=p, pushup(u);
        return;
    }
    if(p.x[k]<=tr[u].P.x[k]) insert(ls, p, k^1);
    else insert(rs, p, k^1);
    pushup(u);
    maintain(u, k);
}

int dis(Point a, Point b){
    return abs(a.x[0]-b.x[0])+abs(a.x[1]-b.x[1]);
}

int H(Node t, Point p){
    int x=p.x[0], y=p.x[1];
    return max(0, t.L[0]-x)+max(0, t.L[1]-y)+max(0, x-t.R[0])+max(0, y-t.R[1]);
}

int res;

void query(int u, Point p){
    if(!u) return;
    res=min(res, dis(tr[u].P, p));
    int LV=INF, RV=INF;
    if(ls) LV=H(tr[ls], p);
    if(rs) RV=H(tr[rs], p);

    if(LV<RV){
        if(LV<res) query(ls, p);
        if(RV<res) query(rs, p);
    }
    else{
        if(RV<res) query(rs, p);
        if(LV<res) query(ls, p);
    }
}

int main(){
    cin>>n>>m;
    // init
    tr[0].L[0]=tr[0].L[1]=N+5;
    tr[0].R[0]=tr[0].R[1]=-1;

    rep(i,1,n){
        int x, y; read(x), read(y);
        pt[i]={x, y};
    }
    root=rebuild(1, n, 0);

    rep(i,1,m){
        int op, x, y; read(op), read(x), read(y);
        if(op==1) insert(root, {x, y}, 0);
        else{
            res=INF;
            query(root, {x, y});
            Write(res);
        }
    }

    return 0;
}
